package doubleLinkedList;

/**
 * 实现带头双向链表
 *
 * 插入节点处理逻辑：
 * 先处理待插入节点的 next 和 prev
 * 再处理 原链表的prev 和 next*/
public class DoubleLinkedList implements IDoubleLinkedListOperation{
    static class ListNode {
        public int val;
        public ListNode next;
        public ListNode prev;
        public ListNode(int val) {
            this.val = val;
        }
    }
    //哨兵位
    ListNode head = new ListNode(-1);

    public ListNode rear = head;
    private int size;//哨兵位不算做有效元素个数

    //头插
    public boolean addFirst(int val) {
        //若链表为null，则head.next.prev 无需修改,否则会出现空指针异常
        ListNode node = new ListNode(val);
        node.prev = this.head;
        node.next = this.head.next;
        //由于是头插，故当链表为空时，头插的节点为尾节点
        //当链表不为空时，需要维护this.head.next.prev
        if(!isEmpty()) {
            this.head.next.prev = node;
        } else {
            this.rear = node;
        }
        this.head.next = node;
        this.size++;
        return true;
    }

    //尾插
    public boolean addLast(int val) {
        ListNode node = new ListNode(val);
        //当链表为空时，在头节点后面进行尾插
        if(isEmpty()) {
            node.prev = this.head;
            node.next = null;
            this.head.next = node;
        } else {
            node.prev = this.rear;
            node.next = null;
            this.rear.next = node;
        }
        this.rear = node;
        this.size++;
        return true;
    }

    //头删
    public boolean removeFirst() {
        //链表为空抛异常并返回false
        if(isEmpty()) {
            try{
                throw new MyDoubleLinkedListException("链表为空，无法进行删除操作！");
            }catch(MyDoubleLinkedListException e) {
                return false;
            }
        }
        ListNode del = this.head.next;
        //若链表中只存在一个节点，直接将head的next节点置空
        if(del.next == null) {
            this.head.next = null;
            this.size--;
            return true;
        }
        //当代码走到此处，说明链表中至少存在两个及以上的节点
        del.next.prev = this.head;
        this.head.next = del.next;
        this.size--;
        return true;
    }

    //尾删
    public boolean removeLast() {
        //对链表判空 若为空则抛异常并返回false
        if(isEmpty()) {
            try{
                throw new MyDoubleLinkedListException("链表为空，无法进行删除操作！");
            }catch(MyDoubleLinkedListException e) {
                return false;
            }
        }
        ListNode del = this.rear;
        this.rear = del.prev;
        this.rear.next = null;
        this.size--;
        return true;
    }

    //链表长度
    public int size() {
        return this.size;
    }

    //查看是否包含key
    public boolean contains(int key) {
        //当findKey方法返回值大于等于零时，说明返回的是有效的下标
        return findKey(key)>=0;
    }

    //清除链表
    public void clear() {
        if(!isEmpty()) {
            ListNode cur = this.head.next;
            while(cur!=null) {
                ListNode nextNode = cur.next;
                cur.prev = null;
                cur.next = null;
                //cur.val = null;
                this.size--;
                cur = nextNode;
            }
        }
        this.rear = null;
        //当将所有节点prev next 置空后，最后需要将哨兵位的next引用置空
        this.head.next = null;
    }

    //判空
    private boolean isEmpty() {
        return this.head.next == null;
    }

    //打印链表-测试使用
    public void display() {
        ListNode cur = this.head.next;
        while(cur!=null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }

    //查找某个元素并返回其下标
    private int findKey(int key) {
        //判空，若为空则返回-1
        if(isEmpty()) {
            return -1;
        }
        ListNode cur = this.head.next;
        for(int i = 0; i < this.size; i++) {
            if(cur.val==key) {
                return i;
            }
            cur = cur.next;
        }
        return -1;
    }
}
